k-Nearest Neighbor ( kNN) algorithm is commonly used in data imputation. It is of poor efficiency because of the similarity computation between every tow records. To solve the efficiency problem, an improved kNN data imputation algorithm combined with Locality Sensitive Hashing (LSH) named LSH- kNN was proposed. First, all the complete records were indexed in LSH way. Then corresponding LSH ways for nominal, numeric and mixed-type incomplete data were put forward, and LSH values for all the incomplete records were computed in the proposed way to find candidate similar records. Finally, the incomplete records' real distance to candidate similar records were calculated, and the top- k similar records for kNN imputation were found. The experimental results show that the proposed method LSH- kNN has higher efficiency than traditional kNN as well as keeping almost the same accuracy.